
import math
from pickle import GLOBAL
N=3
begin_status = [1,2,3,8,5,6,7,4,0]#九宫格初始状态
end_status = [0,1,3,8,2,6,7,5,4]#九宫格结束状态
close_list = []   
open_list = []
move = [N,-N,+1,-1]
1
class Node:
    def __init__(self,status,floor,father):
        '''
        节点函数
        :param status: list 当前状态
        :param floor: int 当前层级
        :param father: Node 父节点 
        '''
        self.status = status
        self.floor = floor
        self.father = father
begin = Node(begin_status,0,None)
end = Node(end_status,0,None)

class search():
    def __init__(self,a):
        self.N = a
        self.all_num = []

    def find(self):
        open_list.append(begin)
        close_list.append(begin)
        p = 0
        q = 1
        a = 0
        for i in range(0,int(math.pow(self.N,2))):
            a = a*10 + begin.status[i]
        self.all_num.append(a)    
        while q>p:
            for node in open_list:
                print(node.status , end=',')
            print('\n')
            close_list.append(open_list[p])
            if self.comp(open_list[p],end):
                loc = open_list[p].status.index(0)
                for i in move:
                    if self.judge(loc,loc+i):
                        if self.trans_add(loc,loc+i,open_list[p]):
                            q+=1
                p+=1
            else:
                return p
        return -1

    def comp(self,x,y):
        for i in range(len(x.status)):
            if x.status[i]!=y.status[i]:
                return True   #如果有不相等的就返回TRUE
        return False      

    def judge(self,x,y):
        if y<0 or y>math.pow(self.N,2)-1:
            return False
        elif x%self.N == (self.N-1) and y%self.N == 0:
            return False
        elif x%self.N == 0 and y%self.N == (self.N-1):
            return False
        else:
            return True      

    def trans_add(self,x,y,p):
        temp = p.status[:]
        temp[x]=p.status[y]
        temp[y]=p.status[x]
        if self.exam(temp):
            new=Node(temp,p.floor+1,p)
            open_list.append(new)
            return True
        else:
            return False
    
    def exam(self,str):
        a = 0
        for i in range(0,int(math.pow(self.N,2))):
            a = a*10+str[i]
        if self.all_num.count(a)>0:
            return False
        else:
            self.all_num.append(a)
            return True 

if __name__ =='__main__':
    a = search(N)
    goal = a.find()
    if goal == -1:
        print("不可达。")
    else:
        step_num = open_list[goal].floor
        print('移动次数:',step_num)
        process=[open_list[goal].status]
        c = open_list[goal]
        for i in range(step_num):
            b = c.father
            process.append(b.status)
            c = b
        real = [process[step_num]]
        print('初始态为:')
        print(process[step_num])
        for i in range(1,step_num+1):
            real.append(process[step_num-i])
            print('step'+str(i)+':')
            print(process[step_num-i])       

        print(real)#最终过程列表
   